/** 
二叉树深度优先遍历
前序遍历： 144.二叉树的前序遍历
后序遍历： 145.二叉树的后序遍历
中序遍历： 94.二叉树的中序遍历
二叉树广度优先遍历
层序遍历：102.二叉树的层序遍历
           5
          / \
         4   6
        / \ / \
       1  2 7  8
前序遍历（中左右）：5 4 1 2 6 7 8
中序遍历（左中右）：1 4 2 5 7 6 8
后序遍历（左右中）：1 2 4 7 8 6 5
*/


// 前序遍历:

var preorderTraversal = function(root, res = []) {
    if (!root) return res;
    res.push(root.val);
    preorderTraversal(root.left, res)
    preorderTraversal(root.right, res)
    return res;
};

var preorderTraversal = function(root) {
    const res = []
    const preorder = (root) => {
        if(!root) return res
        res.push(root.val)
        preorder(root.left)
        preorder(root.right)
    }
    preorder(root)
    return res
};

// 中序遍历:

var inorderTraversal = function(root, res = []) {
    if (!root) return res;
    inorderTraversal(root.left, res);
    res.push(root.val);
    inorderTraversal(root.right, res);
    return res;
};

var inorderTraversal = function(root) {
    let res = []
    const inorder = (root) => {
        if(!root) return res
        inorder(root.left);
        res.push(root.val);
        inorder(root.right);
    }
    inorder(root);
    return res;
};

// 后序遍历:

var postorderTraversal = function(root, res = []) {
    if (!root) return res;
    postorderTraversal(root.left, res);
    postorderTraversal(root.right, res);
    res.push(root.val);
    return res;
};

var postorderTraversal = function(root) {
    let res = []
    const postorder = (root) => {
        if(!root) return res
        postorder(root.left)
        postorder(root.right)
        res.push(root.val)
    }
    postorder(root)
    return res
};